// Copyright (c) 2021, gottingen group.
// All rights reserved.
// Created by liyinbin lijippy@163.com

#include "abel/container/internal/raw_hash_set.h"

#include <cmath>
#include <cstdint>
#include <deque>
#include <functional>
#include <memory>
#include <numeric>
#include <random>
#include <string>

#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "abel/base/profile.h"
#include "abel/chrono/internal/cycle_clock.h"
#include "abel/log/logging.h"
#include "abel/container/internal/container_memory.h"
#include "abel/container/internal/hash_function_defaults.h"
#include "testing/hash_policy_testing.h"
#include "abel/container/internal/hashtable_debug.h"
#include <string_view>

namespace abel {

    namespace container_internal {

        struct RawHashSetTestOnlyAccess {
            template<typename C>
            static auto GetSlots(const C &c) -> decltype(c.slots_) {
                return c.slots_;
            }
        };

        namespace {

            using ::testing::DoubleNear;
            using ::testing::ElementsAre;
            using ::testing::Ge;
            using ::testing::Lt;
            using ::testing::Optional;
            using ::testing::Pair;
            using ::testing::UnorderedElementsAre;

            TEST(Util, normalize_capacity) {
                EXPECT_EQ(1, normalize_capacity(0));
                EXPECT_EQ(1, normalize_capacity(1));
                EXPECT_EQ(3, normalize_capacity(2));
                EXPECT_EQ(3, normalize_capacity(3));
                EXPECT_EQ(7, normalize_capacity(4));
                EXPECT_EQ(7, normalize_capacity(7));
                EXPECT_EQ(15, normalize_capacity(8));
                EXPECT_EQ(15, normalize_capacity(15));
                EXPECT_EQ(15 * 2 + 1, normalize_capacity(15 + 1));
                EXPECT_EQ(15 * 2 + 1, normalize_capacity(15 + 2));
            }

            TEST(Util, GrowthAndCapacity) {
                // Verify that GrowthToCapacity gives the minimum capacity that has enough
                // growth.
                for (size_t growth = 0; growth < 10000; ++growth) {
                    SCOPED_TRACE(growth);
                    size_t capacity = normalize_capacity(GrowthToLowerboundCapacity(growth));
                    // The capacity is large enough for `growth`
                    EXPECT_THAT(capacity_to_growth(capacity), Ge(growth));
                    if (growth != 0 && capacity > 1) {
                        // There is no smaller capacity that works.
                        EXPECT_THAT(capacity_to_growth(capacity / 2), Lt(growth));
                    }
                }

                for (size_t capacity = Group::kWidth - 1; capacity < 10000;
                     capacity = 2 * capacity + 1) {
                    SCOPED_TRACE(capacity);
                    size_t growth = capacity_to_growth(capacity);
                    EXPECT_THAT(growth, Lt(capacity));
                    EXPECT_LE(GrowthToLowerboundCapacity(growth), capacity);
                    EXPECT_EQ(normalize_capacity(GrowthToLowerboundCapacity(growth)), capacity);
                }
            }

            TEST(Util, probe_seq) {
                probe_seq<16> seq(0, 127);
                auto gen = [&]() {
                    size_t res = seq.offset();
                    seq.next();
                    return res;
                };
                std::vector<size_t> offsets(8);
                std::generate_n(offsets.begin(), 8, gen);
                EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64));
                seq = probe_seq<16>(128, 127);
                std::generate_n(offsets.begin(), 8, gen);
                EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64));
            }

            TEST(bit_mask, Smoke) {
                EXPECT_FALSE((bit_mask<uint8_t, 8>(0)));
                EXPECT_TRUE((bit_mask<uint8_t, 8>(5)));

                EXPECT_THAT((bit_mask<uint8_t, 8>(0)), ElementsAre());
                EXPECT_THAT((bit_mask<uint8_t, 8>(0x1)), ElementsAre(0));
                EXPECT_THAT((bit_mask<uint8_t, 8>(0x2)), ElementsAre(1));
                EXPECT_THAT((bit_mask<uint8_t, 8>(0x3)), ElementsAre(0, 1));
                EXPECT_THAT((bit_mask<uint8_t, 8>(0x4)), ElementsAre(2));
                EXPECT_THAT((bit_mask<uint8_t, 8>(0x5)), ElementsAre(0, 2));
                EXPECT_THAT((bit_mask<uint8_t, 8>(0x55)), ElementsAre(0, 2, 4, 6));
                EXPECT_THAT((bit_mask<uint8_t, 8>(0xAA)), ElementsAre(1, 3, 5, 7));
            }

            TEST(bit_mask, WithShift) {
                // See the non-SSE version of Group for details on what this math is for.
                uint64_t ctrl = 0x1716151413121110;
                uint64_t hash = 0x12;
                constexpr uint64_t msbs = 0x8080808080808080ULL;
                constexpr uint64_t lsbs = 0x0101010101010101ULL;
                auto x = ctrl ^(lsbs * hash);
                uint64_t mask = (x - lsbs) & ~x & msbs;
                EXPECT_EQ(0x0000000080800000, mask);

                bit_mask<uint64_t, 8, 3> b(mask);
                EXPECT_EQ(*b, 2);
            }

            TEST(bit_mask, LeadingTrailing) {
                EXPECT_EQ((bit_mask<uint32_t, 16>(0x00001a40).LeadingZeros()), 3);
                EXPECT_EQ((bit_mask<uint32_t, 16>(0x00001a40).TrailingZeros()), 6);

                EXPECT_EQ((bit_mask<uint32_t, 16>(0x00000001).LeadingZeros()), 15);
                EXPECT_EQ((bit_mask<uint32_t, 16>(0x00000001).TrailingZeros()), 0);

                EXPECT_EQ((bit_mask<uint32_t, 16>(0x00008000).LeadingZeros()), 0);
                EXPECT_EQ((bit_mask<uint32_t, 16>(0x00008000).TrailingZeros()), 15);

                EXPECT_EQ((bit_mask<uint64_t, 8, 3>(0x0000008080808000).LeadingZeros()), 3);
                EXPECT_EQ((bit_mask<uint64_t, 8, 3>(0x0000008080808000).TrailingZeros()), 1);

                EXPECT_EQ((bit_mask<uint64_t, 8, 3>(0x0000000000000080).LeadingZeros()), 7);
                EXPECT_EQ((bit_mask<uint64_t, 8, 3>(0x0000000000000080).TrailingZeros()), 0);

                EXPECT_EQ((bit_mask<uint64_t, 8, 3>(0x8000000000000000).LeadingZeros()), 0);
                EXPECT_EQ((bit_mask<uint64_t, 8, 3>(0x8000000000000000).TrailingZeros()), 7);
            }

            TEST(Group, empty_group) {
                for (h2_t h = 0; h != 128; ++h)
                    EXPECT_FALSE(Group{empty_group()}.match(h));
            }

            TEST(Group, match) {
                if (Group::kWidth == 16) {
                    ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7,
                                      7, 5, 3, 1, 1, 1, 1, 1};
                    EXPECT_THAT(Group{group}.match(0), ElementsAre());
                    EXPECT_THAT(Group{group}.match(1), ElementsAre(1, 11, 12, 13, 14, 15));
                    EXPECT_THAT(Group{group}.match(3), ElementsAre(3, 10));
                    EXPECT_THAT(Group{group}.match(5), ElementsAre(5, 9));
                    EXPECT_THAT(Group{group}.match(7), ElementsAre(7, 8));
                } else if (Group::kWidth == 8) {
                    ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};
                    EXPECT_THAT(Group{group}.match(0), ElementsAre());
                    EXPECT_THAT(Group{group}.match(1), ElementsAre(1, 5, 7));
                    EXPECT_THAT(Group{group}.match(2), ElementsAre(2, 4));
                } else {
                    FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth;
                }
            }

            TEST(Group, match_empty) {
                if (Group::kWidth == 16) {
                    ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7,
                                      7, 5, 3, 1, 1, 1, 1, 1};
                    EXPECT_THAT(Group{group}.match_empty(), ElementsAre(0, 4));
                } else if (Group::kWidth == 8) {
                    ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};
                    EXPECT_THAT(Group{group}.match_empty(), ElementsAre(0));
                } else {
                    FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth;
                }
            }

            TEST(Group, match_empty_or_deleted) {
                if (Group::kWidth == 16) {
                    ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7,
                                      7, 5, 3, 1, 1, 1, 1, 1};
                    EXPECT_THAT(Group{group}.match_empty_or_deleted(), ElementsAre(0, 2, 4));
                } else if (Group::kWidth == 8) {
                    ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};
                    EXPECT_THAT(Group{group}.match_empty_or_deleted(), ElementsAre(0, 3));
                } else {
                    FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth;
                }
            }

            TEST(Batch, DropDeletes) {
                constexpr size_t kCapacity = 63;
                constexpr size_t kGroupWidth = container_internal::Group::kWidth;
                std::vector<ctrl_t> ctrl(kCapacity + 1 + kGroupWidth);
                ctrl[kCapacity] = kSentinel;
                std::vector<ctrl_t> pattern = {kEmpty, 2, kDeleted, 2, kEmpty, 1, kDeleted};
                for (size_t i = 0; i != kCapacity; ++i) {
                    ctrl[i] = pattern[i % pattern.size()];
                    if (i < kGroupWidth - 1)
                        ctrl[i + kCapacity + 1] = pattern[i % pattern.size()];
                }
                ConvertDeletedToEmptyAndFullToDeleted(ctrl.data(), kCapacity);
                ASSERT_EQ(ctrl[kCapacity], kSentinel);
                for (size_t i = 0; i < kCapacity + 1 + kGroupWidth; ++i) {
                    ctrl_t expected = pattern[i % (kCapacity + 1) % pattern.size()];
                    if (i == kCapacity)
                        expected = kSentinel;
                    if (expected == kDeleted)
                        expected = kEmpty;
                    if (is_full(expected))
                        expected = kDeleted;
                    EXPECT_EQ(ctrl[i], expected)
                                        << i << " " << int{pattern[i % pattern.size()]};
                }
            }

            TEST(Group, count_leading_empty_or_deleted) {
                const std::vector<ctrl_t> empty_examples = {kEmpty, kDeleted};
                const std::vector<ctrl_t> full_examples = {0, 1, 2, 3, 5, 9, 127, kSentinel};

                for (ctrl_t empty : empty_examples) {
                    std::vector<ctrl_t> e(Group::kWidth, empty);
                    EXPECT_EQ(Group::kWidth, Group{e.data()}.count_leading_empty_or_deleted());
                    for (ctrl_t full : full_examples) {
                        for (size_t i = 0; i != Group::kWidth; ++i) {
                            std::vector<ctrl_t> f(Group::kWidth, empty);
                            f[i] = full;
                            EXPECT_EQ(i, Group{f.data()}.count_leading_empty_or_deleted());
                        }
                        std::vector<ctrl_t> f(Group::kWidth, empty);
                        f[Group::kWidth * 2 / 3] = full;
                        f[Group::kWidth / 2] = full;
                        EXPECT_EQ(
                                Group::kWidth / 2, Group{f.data()}.count_leading_empty_or_deleted());
                    }
                }
            }

            struct IntPolicy {
                using slot_type = int64_t;
                using key_type = int64_t;
                using init_type = int64_t;

                static void construct(void *, int64_t *slot, int64_t v) { *slot = v; }

                static void destroy(void *, int64_t *) {}

                static void transfer(void *, int64_t *new_slot, int64_t *old_slot) {
                    *new_slot = *old_slot;
                }

                static int64_t &element(slot_type *slot) { return *slot; }

                template<class F>
                static auto apply(F &&f, int64_t x) -> decltype(std::forward<F>(f)(x, x)) {
                    return std::forward<F>(f)(x, x);
                }
            };

            class StringPolicy {
                template<class F, class K, class V,
                        class = typename std::enable_if<
                                std::is_convertible<const K &, std::string_view>::value>::type>
                decltype(std::declval<F>()(
                        std::declval<const std::string_view &>(), std::piecewise_construct,
                        std::declval<std::tuple<K>>(),
                        std::declval<V>())) static apply_impl(F &&f,
                                                              std::pair<std::tuple<K>, V> p) {
                    const std::string_view &key = std::get<0>(p.first);
                    return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
                                              std::move(p.second));
                }

            public:
                struct slot_type {
                    struct ctor {
                    };

                    template<class... Ts>
                    slot_type(ctor, Ts &&... ts) : pair(std::forward<Ts>(ts)...) {}

                    std::pair<std::string, std::string> pair;
                };

                using key_type = std::string;
                using init_type = std::pair<std::string, std::string>;

                template<class allocator_type, class... Args>
                static void construct(allocator_type *alloc, slot_type *slot, Args... args) {
                    std::allocator_traits<allocator_type>::construct(
                            *alloc, slot, typename slot_type::ctor(), std::forward<Args>(args)...);
                }

                template<class allocator_type>
                static void destroy(allocator_type *alloc, slot_type *slot) {
                    std::allocator_traits<allocator_type>::destroy(*alloc, slot);
                }

                template<class allocator_type>
                static void transfer(allocator_type *alloc, slot_type *new_slot,
                                     slot_type *old_slot) {
                    construct(alloc, new_slot, std::move(old_slot->pair));
                    destroy(alloc, old_slot);
                }

                static std::pair<std::string, std::string> &element(slot_type *slot) {
                    return slot->pair;
                }

                template<class F, class... Args>
                static auto apply(F &&f, Args &&... args)
                -> decltype(apply_impl(std::forward<F>(f),
                                       PairArgs(std::forward<Args>(args)...))) {
                    return apply_impl(std::forward<F>(f),
                                      PairArgs(std::forward<Args>(args)...));
                }
            };

            struct string_hash : abel::hash<std::string_view> {
                using is_transparent = void;
            };
            struct StringEq : std::equal_to<std::string_view> {
                using is_transparent = void;
            };

            struct StringTable
                    : raw_hash_set<StringPolicy, string_hash, StringEq, std::allocator<int>> {
                using Base = typename StringTable::raw_hash_set;

                StringTable() {}

                using Base::Base;
            };

            struct IntTable
                    : raw_hash_set<IntPolicy, container_internal::hash_default_hash<int64_t>,
                            std::equal_to<int64_t>, std::allocator<int64_t>> {
                using Base = typename IntTable::raw_hash_set;
                using Base::Base;
            };

            template<typename T>
            struct CustomAlloc : std::allocator<T> {
                CustomAlloc() {}

                template<typename U>
                CustomAlloc(const CustomAlloc<U> &other) {}

                template<class U>
                struct rebind {
                    using other = CustomAlloc<U>;
                };
            };

            struct CustomAllocIntTable
                    : raw_hash_set<IntPolicy, container_internal::hash_default_hash<int64_t>,
                            std::equal_to<int64_t>, CustomAlloc<int64_t>> {
                using Base = typename CustomAllocIntTable::raw_hash_set;
                using Base::Base;
            };

            struct BadFastHash {
                template<class T>
                size_t operator()(const T &) const {
                    return 0;
                }
            };

            struct BadTable : raw_hash_set<IntPolicy, BadFastHash, std::equal_to<int>,
                    std::allocator<int>> {
                using Base = typename BadTable::raw_hash_set;

                BadTable() {}

                using Base::Base;
            };

            TEST(Table, EmptyFunctorOptimization) {
                static_assert(std::is_empty<std::equal_to<std::string_view>>::value, "");
                static_assert(std::is_empty<std::allocator<int>>::value, "");

                struct MockTable {
                    void *ctrl;
                    void *slots;
                    size_t size;
                    size_t capacity;
                    size_t growth_left;
                };
                struct StatelessHash {
                    size_t operator()(std::string_view) const { return 0; }
                };
                struct StatefulHash : StatelessHash {
                    size_t dummy;
                };

                EXPECT_EQ(
                        sizeof(MockTable),
                        sizeof(
                                raw_hash_set<StringPolicy, StatelessHash,
                                        std::equal_to<std::string_view>, std::allocator<int>>));

                EXPECT_EQ(
                        sizeof(MockTable) + sizeof(StatefulHash),
                        sizeof(
                                raw_hash_set<StringPolicy, StatefulHash,
                                        std::equal_to<std::string_view>, std::allocator<int>>));
            }

            TEST(Table, Empty) {
                IntTable t;
                EXPECT_EQ(0, t.size());
                EXPECT_TRUE(t.empty());
            }

#ifdef __GNUC__

            template<class T>
            ABEL_FORCE_INLINE void DoNotOptimize(const T &v) {
                asm volatile("" : : "r,m"(v) : "memory");
            }

#endif

            TEST(Table, Prefetch) {
                IntTable t;
                t.emplace(1);
                // Works for both present and absent keys.
                t.prefetch(1);
                t.prefetch(2);

                // Do not run in debug mode, when prefetch is not implemented, or when
                // sanitizers are enabled, or on WebAssembly.
#if defined(NDEBUG) && defined(__GNUC__) && defined(__x86_64__) && \
    !defined(ADDRESS_SANITIZER) && !defined(MEMORY_SANITIZER) && \
    !defined(THREAD_SANITIZER) && !defined(UNDEFINED_BEHAVIOR_SANITIZER) && \
    !defined(__EMSCRIPTEN__)
                const auto now = [] { return abel::cycle_clock::now(); };

                // Make size enough to not fit in L2 cache (16.7 Mb)
                static constexpr int size = 1 << 22;
                for (int i = 0; i < size; ++i) t.insert(i);

                int64_t no_prefetch = 0, prefetch = 0;
                for (int iter = 0; iter < 10; ++iter) {
                  int64_t time = now();
                  for (int i = 0; i < size; ++i) {
                    DoNotOptimize(t.find(i));
                  }
                  no_prefetch += now() - time;

                  time = now();
                  for (int i = 0; i < size; ++i) {
                    t.prefetch(i + 20);
                    DoNotOptimize(t.find(i));
                  }
                  prefetch += now() - time;
                }

                // no_prefetch is at least 30% slower.
                EXPECT_GE(1.0 * no_prefetch / prefetch, 1.3);
#endif
            }

            TEST(Table, LookupEmpty) {
                IntTable t;
                auto it = t.find(0);
                EXPECT_TRUE(it == t.end());
            }

            TEST(Table, Insert1) {
                IntTable t;
                EXPECT_TRUE(t.find(0) == t.end());
                auto res = t.emplace(0);
                EXPECT_TRUE(res.second);
                EXPECT_THAT(*res.first, 0);
                EXPECT_EQ(1, t.size());
                EXPECT_THAT(*t.find(0), 0);
            }

            TEST(Table, Insert2) {
                IntTable t;
                EXPECT_TRUE(t.find(0) == t.end());
                auto res = t.emplace(0);
                EXPECT_TRUE(res.second);
                EXPECT_THAT(*res.first, 0);
                EXPECT_EQ(1, t.size());
                EXPECT_TRUE(t.find(1) == t.end());
                res = t.emplace(1);
                EXPECT_TRUE(res.second);
                EXPECT_THAT(*res.first, 1);
                EXPECT_EQ(2, t.size());
                EXPECT_THAT(*t.find(0), 0);
                EXPECT_THAT(*t.find(1), 1);
            }

            TEST(Table, InsertCollision) {
                BadTable t;
                EXPECT_TRUE(t.find(1) == t.end());
                auto res = t.emplace(1);
                EXPECT_TRUE(res.second);
                EXPECT_THAT(*res.first, 1);
                EXPECT_EQ(1, t.size());

                EXPECT_TRUE(t.find(2) == t.end());
                res = t.emplace(2);
                EXPECT_THAT(*res.first, 2);
                EXPECT_TRUE(res.second);
                EXPECT_EQ(2, t.size());

                EXPECT_THAT(*t.find(1), 1);
                EXPECT_THAT(*t.find(2), 2);
            }

// Test that we do not add existent element in case we need to search through
// many groups with deleted elements
            TEST(Table, InsertCollisionAndFindAfterDelete) {
                BadTable t;  // all elements go to the same group.
                // Have at least 2 groups with Group::kWidth collisions
                // plus some extra collisions in the last group.
                constexpr size_t kNumInserts = Group::kWidth * 2 + 5;
                for (size_t i = 0; i < kNumInserts; ++i) {
                    auto res = t.emplace(i);
                    EXPECT_TRUE(res.second);
                    EXPECT_THAT(*res.first, i);
                    EXPECT_EQ(i + 1, t.size());
                }

                // Remove elements one by one and check
                // that we still can find all other elements.
                for (size_t i = 0; i < kNumInserts; ++i) {
                    EXPECT_EQ(1, t.erase(i)) << i;
                    for (size_t j = i + 1; j < kNumInserts; ++j) {
                        EXPECT_THAT(*t.find(j), j);
                        auto res = t.emplace(j);
                        EXPECT_FALSE(res.second) << i << " " << j;
                        EXPECT_THAT(*res.first, j);
                        EXPECT_EQ(kNumInserts - i - 1, t.size());
                    }
                }
                EXPECT_TRUE(t.empty());
            }

            TEST(Table, LazyEmplace) {
                StringTable t;
                bool called = false;
                auto it = t.lazy_emplace("abc", [&](const StringTable::constructor &f) {
                    called = true;
                    f("abc", "ABC");
                });
                EXPECT_TRUE(called);
                EXPECT_THAT(*it, Pair("abc", "ABC"));
                called = false;
                it = t.lazy_emplace("abc", [&](const StringTable::constructor &f) {
                    called = true;
                    f("abc", "DEF");
                });
                EXPECT_FALSE(called);
                EXPECT_THAT(*it, Pair("abc", "ABC"));
            }

            TEST(Table, ContainsEmpty) {
                IntTable t;

                EXPECT_FALSE(t.contains(0));
            }

            TEST(Table, Contains1) {
                IntTable t;

                EXPECT_TRUE(t.insert(0).second);
                EXPECT_TRUE(t.contains(0));
                EXPECT_FALSE(t.contains(1));

                EXPECT_EQ(1, t.erase(0));
                EXPECT_FALSE(t.contains(0));
            }

            TEST(Table, Contains2) {
                IntTable t;

                EXPECT_TRUE(t.insert(0).second);
                EXPECT_TRUE(t.contains(0));
                EXPECT_FALSE(t.contains(1));

                t.clear();
                EXPECT_FALSE(t.contains(0));
            }

            int decompose_constructed;

            struct DecomposeType {
                DecomposeType(int i) : i(i) {  // NOLINT
                    ++decompose_constructed;
                }

                explicit DecomposeType(const char *d) : DecomposeType(*d) {}

                int i;
            };

            struct DecomposeHash {
                using is_transparent = void;

                size_t operator()(DecomposeType a) const { return a.i; }

                size_t operator()(int a) const { return a; }

                size_t operator()(const char *a) const { return *a; }
            };

            struct DecomposeEq {
                using is_transparent = void;

                bool operator()(DecomposeType a, DecomposeType b) const { return a.i == b.i; }

                bool operator()(DecomposeType a, int b) const { return a.i == b; }

                bool operator()(DecomposeType a, const char *b) const { return a.i == *b; }
            };

            struct DecomposePolicy {
                using slot_type = DecomposeType;
                using key_type = DecomposeType;
                using init_type = DecomposeType;

                template<typename T>
                static void construct(void *, DecomposeType *slot, T &&v) {
                    *slot = DecomposeType(std::forward<T>(v));
                }

                static void destroy(void *, DecomposeType *) {}

                static DecomposeType &element(slot_type *slot) { return *slot; }

                template<class F, class T>
                static auto apply(F &&f, const T &x) -> decltype(std::forward<F>(f)(x, x)) {
                    return std::forward<F>(f)(x, x);
                }
            };

            template<typename Hash, typename Eq>
            void TestDecompose(bool construct_three) {
                DecomposeType elem{0};
                const int one = 1;
                const char *three_p = "3";
                const auto &three = three_p;

                raw_hash_set<DecomposePolicy, Hash, Eq, std::allocator<int>> set1;

                decompose_constructed = 0;
                int expected_constructed = 0;
                EXPECT_EQ(expected_constructed, decompose_constructed);
                set1.insert(elem);
                EXPECT_EQ(expected_constructed, decompose_constructed);
                set1.insert(1);
                EXPECT_EQ(++expected_constructed, decompose_constructed);
                set1.emplace("3");
                EXPECT_EQ(++expected_constructed, decompose_constructed);
                EXPECT_EQ(expected_constructed, decompose_constructed);

                {  // insert(T&&)
                    set1.insert(1);
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                }

                {  // insert(const T&)
                    set1.insert(one);
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                }

                {  // insert(hint, T&&)
                    set1.insert(set1.begin(), 1);
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                }

                {  // insert(hint, const T&)
                    set1.insert(set1.begin(), one);
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                }

                {  // emplace(...)
                    set1.emplace(1);
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                    set1.emplace("3");
                    expected_constructed += construct_three;
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                    set1.emplace(one);
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                    set1.emplace(three);
                    expected_constructed += construct_three;
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                }

                {  // emplace_hint(...)
                    set1.emplace_hint(set1.begin(), 1);
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                    set1.emplace_hint(set1.begin(), "3");
                    expected_constructed += construct_three;
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                    set1.emplace_hint(set1.begin(), one);
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                    set1.emplace_hint(set1.begin(), three);
                    expected_constructed += construct_three;
                    EXPECT_EQ(expected_constructed, decompose_constructed);
                }
            }

            TEST(Table, Decompose) {
                TestDecompose<DecomposeHash, DecomposeEq>(false);

                struct TransparentHashIntOverload {
                    size_t operator()(DecomposeType a) const { return a.i; }

                    size_t operator()(int a) const { return a; }
                };
                struct TransparentEqIntOverload {
                    bool operator()(DecomposeType a, DecomposeType b) const {
                        return a.i == b.i;
                    }

                    bool operator()(DecomposeType a, int b) const { return a.i == b; }
                };
                TestDecompose<TransparentHashIntOverload, DecomposeEq>(true);
                TestDecompose<TransparentHashIntOverload, TransparentEqIntOverload>(true);
                TestDecompose<DecomposeHash, TransparentEqIntOverload>(true);
            }

// Returns the largest m such that a table with m elements has the same number
// of buckets as a table with n elements.
            size_t MaxDensitySize(size_t n) {
                IntTable t;
                t.reserve(n);
                for (size_t i = 0; i != n; ++i)
                    t.emplace(i);
                const size_t c = t.bucket_count();
                while (c == t.bucket_count())
                    t.emplace(n++);
                return t.size() - 1;
            }

            struct Modulo1000Hash {
                size_t operator()(int x) const { return x % 1000; }
            };

            struct Modulo1000HashTable
                    : public raw_hash_set<IntPolicy, Modulo1000Hash, std::equal_to<int>,
                            std::allocator<int>> {
            };

// Test that rehash with no resize happen in case of many deleted slots.
            TEST(Table, RehashWithNoResize) {
                Modulo1000HashTable t;
                // Adding the same length (and the same hash) strings
                // to have at least kMinFullGroups groups
                // with Group::kWidth collisions. Then fill up to MaxDensitySize;
                const size_t kMinFullGroups = 7;
                std::vector<int> keys;
                for (size_t i = 0; i < MaxDensitySize(Group::kWidth * kMinFullGroups); ++i) {
                    int k = i * 1000;
                    t.emplace(k);
                    keys.push_back(k);
                }
                const size_t capacity = t.capacity();

                // Remove elements from all groups except the first and the last one.
                // All elements removed from full groups will be marked as kDeleted.
                const size_t erase_begin = Group::kWidth / 2;
                const size_t erase_end = (t.size() / Group::kWidth - 1) * Group::kWidth;
                for (size_t i = erase_begin; i < erase_end; ++i) {
                    EXPECT_EQ(1, t.erase(keys[i])) << i;
                }
                keys.erase(keys.begin() + erase_begin, keys.begin() + erase_end);

                auto last_key = keys.back();
                size_t last_key_num_probes = get_hashtable_debug_num_probes(t, last_key);

                // Make sure that we have to make a lot of probes for last key.
                ASSERT_GT(last_key_num_probes, kMinFullGroups);

                int x = 1;
                // Insert and erase one element, before inplace rehash happen.
                while (last_key_num_probes == get_hashtable_debug_num_probes(t, last_key)) {
                    t.emplace(x);
                    ASSERT_EQ(capacity, t.capacity());
                    // All elements should be there.
                    ASSERT_TRUE(t.find(x) != t.end()) << x;
                    for (const auto &k : keys) {
                        ASSERT_TRUE(t.find(k) != t.end()) << k;
                    }
                    t.erase(x);
                    ++x;
                }
            }

            TEST(Table, InsertEraseStressTest) {
                IntTable t;
                const size_t kMinElementCount = 250;
                std::deque<int> keys;
                size_t i = 0;
                for (; i < MaxDensitySize(kMinElementCount); ++i) {
                    t.emplace(i);
                    keys.push_back(i);
                }
                const size_t kNumIterations = 1000000;
                for (; i < kNumIterations; ++i) {
                    ASSERT_EQ(1, t.erase(keys.front()));
                    keys.pop_front();
                    t.emplace(i);
                    keys.push_back(i);
                }
            }

            TEST(Table, InsertOverloads) {
                StringTable t;
                // These should all trigger the insert(init_type) overload.
                t.insert({{},
                          {}});
                t.insert({"ABC", {}});
                t.insert({"DEF", "!!!"});

                EXPECT_THAT(t, UnorderedElementsAre(Pair("", ""), Pair("ABC", ""),
                                                    Pair("DEF", "!!!")));
            }

            TEST(Table, LargeTable) {
                IntTable t;
                for (int64_t i = 0; i != 100000; ++i)
                    t.emplace(i << 40);
                for (int64_t i = 0; i != 100000; ++i)
                    ASSERT_EQ(i << 40, *t.find(i << 40));
            }

// Timeout if copy is quadratic as it was in Rust.
            TEST(Table, EnsureNonQuadraticAsInRust) {
                static const size_t kLargeSize = 1 << 15;

                IntTable t;
                for (size_t i = 0; i != kLargeSize; ++i) {
                    t.insert(i);
                }

                // If this is quadratic, the test will timeout.
                IntTable t2;
                for (const auto &entry : t)
                    t2.insert(entry);
            }

            TEST(Table, ClearBug) {
                IntTable t;
                constexpr size_t capacity = container_internal::Group::kWidth - 1;
                constexpr size_t max_size = capacity / 2 + 1;
                for (size_t i = 0; i < max_size; ++i) {
                    t.insert(i);
                }
                ASSERT_EQ(capacity, t.capacity());
                intptr_t original = reinterpret_cast<intptr_t>(&*t.find(2));
                t.clear();
                ASSERT_EQ(capacity, t.capacity());
                for (size_t i = 0; i < max_size; ++i) {
                    t.insert(i);
                }
                ASSERT_EQ(capacity, t.capacity());
                intptr_t second = reinterpret_cast<intptr_t>(&*t.find(2));
                // We are checking that original and second are close enough to each other
                // that they are probably still in the same group.  This is not strictly
                // guaranteed.
                EXPECT_LT(std::abs(original - second),
                          capacity * sizeof(IntTable::value_type));
            }

            TEST(Table, Erase) {
                IntTable t;
                EXPECT_TRUE(t.find(0) == t.end());
                auto res = t.emplace(0);
                EXPECT_TRUE(res.second);
                EXPECT_EQ(1, t.size());
                t.erase(res.first);
                EXPECT_EQ(0, t.size());
                EXPECT_TRUE(t.find(0) == t.end());
            }

            TEST(Table, EraseMaintainsValidIterator) {
                IntTable t;
                const int kNumElements = 100;
                for (int i = 0; i < kNumElements; i++) {
                    EXPECT_TRUE(t.emplace(i).second);
                }
                EXPECT_EQ(t.size(), kNumElements);

                int num_erase_calls = 0;
                auto it = t.begin();
                while (it != t.end()) {
                    t.erase(it++);
                    num_erase_calls++;
                }

                EXPECT_TRUE(t.empty());
                EXPECT_EQ(num_erase_calls, kNumElements);
            }

// Collect N bad keys by following algorithm:
// 1. Create an empty table and reserve it to 2 * N.
// 2. Insert N random elements.
// 3. Take first Group::kWidth - 1 to bad_keys array.
// 4. Clear the table without resize.
// 5. Go to point 2 while N keys not collected
            std::vector<int64_t> CollectBadMergeKeys(size_t N) {
                static constexpr int kGroupSize = Group::kWidth - 1;

                auto topk_range = [](size_t b, size_t e, IntTable *t) -> std::vector<int64_t> {
                    for (size_t i = b; i != e; ++i) {
                        t->emplace(i);
                    }
                    std::vector<int64_t> res;
                    res.reserve(kGroupSize);
                    auto it = t->begin();
                    for (size_t i = b; i != e && i != b + kGroupSize; ++i, ++it) {
                        res.push_back(*it);
                    }
                    return res;
                };

                std::vector<int64_t> bad_keys;
                bad_keys.reserve(N);
                IntTable t;
                t.reserve(N * 2);

                for (size_t b = 0; bad_keys.size() < N; b += N) {
                    auto keys = topk_range(b, b + N, &t);
                    bad_keys.insert(bad_keys.end(), keys.begin(), keys.end());
                    t.erase(t.begin(), t.end());
                    EXPECT_TRUE(t.empty());
                }
                return bad_keys;
            }

            struct ProbeStats {
                // Number of elements with specific probe length over all tested tables.
                std::vector<size_t> all_probes_histogram;
                // Ratios total_probe_length/size for every tested table.
                std::vector<double> single_table_ratios;

/*
  friend ProbeStats operator+(const ProbeStats& a, const ProbeStats& b) {
    ProbeStats res = a;
    res.all_probes_histogram.resize(std::max(res.all_probes_histogram.size(),
                                             b.all_probes_histogram.size()));
    std::transform(b.all_probes_histogram.begin(), b.all_probes_histogram.end(),
                   res.all_probes_histogram.begin(),
                   res.all_probes_histogram.begin(), std::plus<size_t>());
    res.single_table_ratios.insert(res.single_table_ratios.end(),
                                   b.single_table_ratios.begin(),
                                   b.single_table_ratios.end());
    return res;
  }
*/
                // Average ratio total_probe_length/size over tables.
                double AvgRatio() const {
                    return std::accumulate(single_table_ratios.begin(),
                                           single_table_ratios.end(), 0.0) /
                           single_table_ratios.size();
                }

                // Maximum ratio total_probe_length/size over tables.
                double MaxRatio() const {
                    return *std::max_element(single_table_ratios.begin(),
                                             single_table_ratios.end());
                }

                // Percentile ratio total_probe_length/size over tables.
                double PercentileRatio(double Percentile = 0.95) const {
                    auto r = single_table_ratios;
                    auto mid = r.begin() + static_cast<size_t>(r.size() * Percentile);
                    if (mid != r.end()) {
                        std::nth_element(r.begin(), mid, r.end());
                        return *mid;
                    } else {
                        return MaxRatio();
                    }
                }

                // Maximum probe length over all elements and all tables.
                size_t MaxProbe() const { return all_probes_histogram.size(); }

                // Fraction of elements with specified probe length.
                std::vector<double> ProbeNormalizedHistogram() const {
                    double total_elements = std::accumulate(all_probes_histogram.begin(),
                                                            all_probes_histogram.end(), 0ull);
                    std::vector<double> res;
                    for (size_t p : all_probes_histogram) {
                        res.push_back(p / total_elements);
                    }
                    return res;
                }

                size_t PercentileProbe(double Percentile = 0.99) const {
                    size_t idx = 0;
                    for (double p : ProbeNormalizedHistogram()) {
                        if (Percentile > p) {
                            Percentile -= p;
                            ++idx;
                        } else {
                            return idx;
                        }
                    }
                    return idx;
                }

                friend std::ostream &operator<<(std::ostream &out, const ProbeStats &s) {
                    out << "{AvgRatio:" << s.AvgRatio() << ", MaxRatio:" << s.MaxRatio()
                        << ", PercentileRatio:" << s.PercentileRatio()
                        << ", MaxProbe:" << s.MaxProbe() << ", Probes=[";
                    for (double p : s.ProbeNormalizedHistogram()) {
                        out << p << ",";
                    }
                    out << "]}";

                    return out;
                }
            };

            struct ExpectedStats {
                double avg_ratio;
                double max_ratio;
                std::vector<std::pair<double, double>> pecentile_ratios;
                std::vector<std::pair<double, double>> pecentile_probes;

/*
  friend std::ostream& operator<<(std::ostream& out, const ExpectedStats& s) {
    out << "{AvgRatio:" << s.avg_ratio << ", MaxRatio:" << s.max_ratio
        << ", PercentileRatios: [";
    for (auto el : s.pecentile_ratios) {
      out << el.first << ":" << el.second << ", ";
    }
    out << "], PercentileProbes: [";
    for (auto el : s.pecentile_probes) {
      out << el.first << ":" << el.second << ", ";
    }
    out << "]}";

    return out;
  }
  */
            };

            void VerifyStats(size_t size, const ExpectedStats &exp,
                             const ProbeStats &stats) {
                EXPECT_LT(stats.AvgRatio(), exp.avg_ratio) << size << " " << stats;
                EXPECT_LT(stats.MaxRatio(), exp.max_ratio) << size << " " << stats;
                for (auto pr : exp.pecentile_ratios) {
                    EXPECT_LE(stats.PercentileRatio(pr.first), pr.second)
                                        << size << " " << pr.first << " " << stats;
                }

                for (auto pr : exp.pecentile_probes) {
                    EXPECT_LE(stats.PercentileProbe(pr.first), pr.second)
                                        << size << " " << pr.first << " " << stats;
                }
            }

            using ProbeStatsPerSize = std::map<size_t, ProbeStats>;

// Collect total ProbeStats on num_iters iterations of the following algorithm:
// 1. Create new table and reserve it to keys.size() * 2
// 2. Insert all keys xored with seed
// 3. Collect ProbeStats from final table.
            ProbeStats CollectProbeStatsOnKeysXoredWithSeed(const std::vector<int64_t> &keys,
                                                            size_t num_iters) {
                const size_t reserve_size = keys.size() * 2;

                ProbeStats stats;

                int64_t seed = 0x71b1a19b907d6e33;
                while (num_iters--) {
                    seed = static_cast<int64_t>(static_cast<uint64_t>(seed) * 17 + 13);
                    IntTable t1;
                    t1.reserve(reserve_size);
                    for (const auto &key : keys) {
                        t1.emplace(key ^ seed);
                    }

                    auto probe_histogram = get_hashtable_debug_num_probes_histogram(t1);
                    stats.all_probes_histogram.resize(
                            std::max(stats.all_probes_histogram.size(), probe_histogram.size()));
                    std::transform(probe_histogram.begin(), probe_histogram.end(),
                                   stats.all_probes_histogram.begin(),
                                   stats.all_probes_histogram.begin(), std::plus<size_t>());

                    size_t total_probe_seq_length = 0;
                    for (size_t i = 0; i < probe_histogram.size(); ++i) {
                        total_probe_seq_length += i * probe_histogram[i];
                    }
                    stats.single_table_ratios.push_back(total_probe_seq_length * 1.0 /
                                                        keys.size());
                    t1.erase(t1.begin(), t1.end());
                }
                return stats;
            }

            ExpectedStats XorSeedExpectedStats() {
                constexpr bool kRandomizesInserts =
#ifdef NDEBUG
                        false;
#else   // NDEBUG
                        true;
#endif  // NDEBUG

                // The effective load factor is larger in non-opt mode because we insert
                // elements out of order.
                switch (container_internal::Group::kWidth) {
                    case 8:
                        if (kRandomizesInserts) {
                            return {0.05,
                                    1.0,
                                    {{0.95, 0.5}},
                                    {{0.95, 0}, {0.99, 2}, {0.999, 4}, {0.9999, 10}}};
                        } else {
                            return {0.05,
                                    2.0,
                                    {{0.95, 0.1}},
                                    {{0.95, 0}, {0.99, 2}, {0.999, 4}, {0.9999, 10}}};
                        }
                    case 16:
                        if (kRandomizesInserts) {
                            return {0.1,
                                    1.0,
                                    {{0.95, 0.1}},
                                    {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};
                        } else {
                            return {0.05,
                                    1.0,
                                    {{0.95, 0.05}},
                                    {{0.95, 0}, {0.99, 1}, {0.999, 4}, {0.9999, 10}}};
                        }
                }
                DLOG_CRITICAL("Unknown Group width");
                return {};
            }

            TEST(Table, DISABLED_EnsureNonQuadraticTopNXorSeedByProbeSeqLength) {
                ProbeStatsPerSize stats;
                std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};
                for (size_t size : sizes) {
                    stats[size] =
                            CollectProbeStatsOnKeysXoredWithSeed(CollectBadMergeKeys(size), 200);
                }
                auto expected = XorSeedExpectedStats();
                for (size_t size : sizes) {
                    auto &stat = stats[size];
                    VerifyStats(size, expected, stat);
                }
            }

// Collect total ProbeStats on num_iters iterations of the following algorithm:
// 1. Create new table
// 2. Select 10% of keys and insert 10 elements key * 17 + j * 13
// 3. Collect ProbeStats from final table
            ProbeStats CollectProbeStatsOnLinearlyTransformedKeys(
                    const std::vector<int64_t> &keys, size_t num_iters) {
                ProbeStats stats;

                std::random_device rd;
                std::mt19937 rng(rd());
                auto linear_transform = [](size_t x, size_t y) { return x * 17 + y * 13; };
                std::uniform_int_distribution<size_t> dist(0, keys.size() - 1);
                while (num_iters--) {
                    IntTable t1;
                    size_t num_keys = keys.size() / 10;
                    size_t start = dist(rng);
                    for (size_t i = 0; i != num_keys; ++i) {
                        for (size_t j = 0; j != 10; ++j) {
                            t1.emplace(linear_transform(keys[(i + start) % keys.size()], j));
                        }
                    }

                    auto probe_histogram = get_hashtable_debug_num_probes_histogram(t1);
                    stats.all_probes_histogram.resize(
                            std::max(stats.all_probes_histogram.size(), probe_histogram.size()));
                    std::transform(probe_histogram.begin(), probe_histogram.end(),
                                   stats.all_probes_histogram.begin(),
                                   stats.all_probes_histogram.begin(), std::plus<size_t>());

                    size_t total_probe_seq_length = 0;
                    for (size_t i = 0; i < probe_histogram.size(); ++i) {
                        total_probe_seq_length += i * probe_histogram[i];
                    }
                    stats.single_table_ratios.push_back(total_probe_seq_length * 1.0 /
                                                        t1.size());
                    t1.erase(t1.begin(), t1.end());
                }
                return stats;
            }

            ExpectedStats LinearTransformExpectedStats() {
                constexpr bool kRandomizesInserts =
#ifdef NDEBUG
                        false;
#else   // NDEBUG
                        true;
#endif  // NDEBUG

                // The effective load factor is larger in non-opt mode because we insert
                // elements out of order.
                switch (container_internal::Group::kWidth) {
                    case 8:
                        if (kRandomizesInserts) {
                            return {0.1,
                                    0.5,
                                    {{0.95, 0.3}},
                                    {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};
                        } else {
                            return {0.15,
                                    0.5,
                                    {{0.95, 0.3}},
                                    {{0.95, 0}, {0.99, 3}, {0.999, 15}, {0.9999, 25}}};
                        }
                    case 16:
                        if (kRandomizesInserts) {
                            return {0.1,
                                    0.4,
                                    {{0.95, 0.3}},
                                    {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};
                        } else {
                            return {0.05,
                                    0.2,
                                    {{0.95, 0.1}},
                                    {{0.95, 0}, {0.99, 1}, {0.999, 6}, {0.9999, 10}}};
                        }
                }
                DLOG_CRITICAL("Unknown Group width");
                return {};
            }

            TEST(Table, DISABLED_EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) {
                ProbeStatsPerSize stats;
                std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};
                for (size_t size : sizes) {
                    stats[size] = CollectProbeStatsOnLinearlyTransformedKeys(
                            CollectBadMergeKeys(size), 300);
                }
                auto expected = LinearTransformExpectedStats();
                for (size_t size : sizes) {
                    auto &stat = stats[size];
                    VerifyStats(size, expected, stat);
                }
            }

            TEST(Table, EraseCollision) {
                BadTable t;

                // 1 2 3
                t.emplace(1);
                t.emplace(2);
                t.emplace(3);
                EXPECT_THAT(*t.find(1), 1);
                EXPECT_THAT(*t.find(2), 2);
                EXPECT_THAT(*t.find(3), 3);
                EXPECT_EQ(3, t.size());

                // 1 DELETED 3
                t.erase(t.find(2));
                EXPECT_THAT(*t.find(1), 1);
                EXPECT_TRUE(t.find(2) == t.end());
                EXPECT_THAT(*t.find(3), 3);
                EXPECT_EQ(2, t.size());

                // DELETED DELETED 3
                t.erase(t.find(1));
                EXPECT_TRUE(t.find(1) == t.end());
                EXPECT_TRUE(t.find(2) == t.end());
                EXPECT_THAT(*t.find(3), 3);
                EXPECT_EQ(1, t.size());

                // DELETED DELETED DELETED
                t.erase(t.find(3));
                EXPECT_TRUE(t.find(1) == t.end());
                EXPECT_TRUE(t.find(2) == t.end());
                EXPECT_TRUE(t.find(3) == t.end());
                EXPECT_EQ(0, t.size());
            }

            TEST(Table, EraseInsertProbing) {
                BadTable t(100);

                // 1 2 3 4
                t.emplace(1);
                t.emplace(2);
                t.emplace(3);
                t.emplace(4);

                // 1 DELETED 3 DELETED
                t.erase(t.find(2));
                t.erase(t.find(4));

                // 1 10 3 11 12
                t.emplace(10);
                t.emplace(11);
                t.emplace(12);

                EXPECT_EQ(5, t.size());
                EXPECT_THAT(t, UnorderedElementsAre(1, 10, 3, 11, 12));
            }

            TEST(Table, Clear) {
                IntTable t;
                EXPECT_TRUE(t.find(0) == t.end());
                t.clear();
                EXPECT_TRUE(t.find(0) == t.end());
                auto res = t.emplace(0);
                EXPECT_TRUE(res.second);
                EXPECT_EQ(1, t.size());
                t.clear();
                EXPECT_EQ(0, t.size());
                EXPECT_TRUE(t.find(0) == t.end());
            }

            TEST(Table, Swap) {
                IntTable t;
                EXPECT_TRUE(t.find(0) == t.end());
                auto res = t.emplace(0);
                EXPECT_TRUE(res.second);
                EXPECT_EQ(1, t.size());
                IntTable u;
                t.swap(u);
                EXPECT_EQ(0, t.size());
                EXPECT_EQ(1, u.size());
                EXPECT_TRUE(t.find(0) == t.end());
                EXPECT_THAT(*u.find(0), 0);
            }

            TEST(Table, Rehash) {
                IntTable t;
                EXPECT_TRUE(t.find(0) == t.end());
                t.emplace(0);
                t.emplace(1);
                EXPECT_EQ(2, t.size());
                t.rehash(128);
                EXPECT_EQ(2, t.size());
                EXPECT_THAT(*t.find(0), 0);
                EXPECT_THAT(*t.find(1), 1);
            }

            TEST(Table, RehashDoesNotRehashWhenNotNecessary) {
                IntTable t;
                t.emplace(0);
                t.emplace(1);
                auto *p = &*t.find(0);
                t.rehash(1);
                EXPECT_EQ(p, &*t.find(0));
            }

            TEST(Table, RehashZeroDoesNotAllocateOnEmptyTable) {
                IntTable t;
                t.rehash(0);
                EXPECT_EQ(0, t.bucket_count());
            }

            TEST(Table, RehashZeroDeallocatesEmptyTable) {
                IntTable t;
                t.emplace(0);
                t.clear();
                EXPECT_NE(0, t.bucket_count());
                t.rehash(0);
                EXPECT_EQ(0, t.bucket_count());
            }

            TEST(Table, RehashZeroForcesRehash) {
                IntTable t;
                t.emplace(0);
                t.emplace(1);
                auto *p = &*t.find(0);
                t.rehash(0);
                EXPECT_NE(p, &*t.find(0));
            }

            TEST(Table, ConstructFromInitList) {
                using P = std::pair<std::string, std::string>;
                struct Q {
                    operator P() const { return {}; }
                };
                StringTable t = {P(), Q(), {}, {{}, {}}};
            }

            TEST(Table, CopyConstruct) {
                IntTable t;
                t.emplace(0);
                EXPECT_EQ(1, t.size());
                {
                    IntTable u(t);
                    EXPECT_EQ(1, u.size());
                    EXPECT_THAT(*u.find(0), 0);
                }
                {
                    IntTable u{t};
                    EXPECT_EQ(1, u.size());
                    EXPECT_THAT(*u.find(0), 0);
                }
                {
                    IntTable u = t;
                    EXPECT_EQ(1, u.size());
                    EXPECT_THAT(*u.find(0), 0);
                }
            }

            TEST(Table, CopyConstructWithAlloc) {
                StringTable t;
                t.emplace("a", "b");
                EXPECT_EQ(1, t.size());
                StringTable u(t, Alloc<std::pair<std::string, std::string>>());
                EXPECT_EQ(1, u.size());
                EXPECT_THAT(*u.find("a"), Pair("a", "b"));
            }

            struct ExplicitAllocIntTable
                    : raw_hash_set<IntPolicy, container_internal::hash_default_hash<int64_t>,
                            std::equal_to<int64_t>, Alloc<int64_t>> {
                ExplicitAllocIntTable() {}
            };

            TEST(Table, AllocWithExplicitCtor) {
                ExplicitAllocIntTable t;
                EXPECT_EQ(0, t.size());
            }

            TEST(Table, MoveConstruct) {
                {
                    StringTable t;
                    t.emplace("a", "b");
                    EXPECT_EQ(1, t.size());

                    StringTable u(std::move(t));
                    EXPECT_EQ(1, u.size());
                    EXPECT_THAT(*u.find("a"), Pair("a", "b"));
                }
                {
                    StringTable t;
                    t.emplace("a", "b");
                    EXPECT_EQ(1, t.size());

                    StringTable u{std::move(t)};
                    EXPECT_EQ(1, u.size());
                    EXPECT_THAT(*u.find("a"), Pair("a", "b"));
                }
                {
                    StringTable t;
                    t.emplace("a", "b");
                    EXPECT_EQ(1, t.size());

                    StringTable u = std::move(t);
                    EXPECT_EQ(1, u.size());
                    EXPECT_THAT(*u.find("a"), Pair("a", "b"));
                }
            }

            TEST(Table, MoveConstructWithAlloc) {
                StringTable t;
                t.emplace("a", "b");
                EXPECT_EQ(1, t.size());
                StringTable u(std::move(t), Alloc<std::pair<std::string, std::string>>());
                EXPECT_EQ(1, u.size());
                EXPECT_THAT(*u.find("a"), Pair("a", "b"));
            }

            TEST(Table, CopyAssign) {
                StringTable t;
                t.emplace("a", "b");
                EXPECT_EQ(1, t.size());
                StringTable u;
                u = t;
                EXPECT_EQ(1, u.size());
                EXPECT_THAT(*u.find("a"), Pair("a", "b"));
            }

            TEST(Table, CopySelfAssign) {
                StringTable t;
                t.emplace("a", "b");
                EXPECT_EQ(1, t.size());
                t = *&t;
                EXPECT_EQ(1, t.size());
                EXPECT_THAT(*t.find("a"), Pair("a", "b"));
            }

            TEST(Table, MoveAssign) {
                StringTable t;
                t.emplace("a", "b");
                EXPECT_EQ(1, t.size());
                StringTable u;
                u = std::move(t);
                EXPECT_EQ(1, u.size());
                EXPECT_THAT(*u.find("a"), Pair("a", "b"));
            }

            TEST(Table, Equality) {
                StringTable t;
                std::vector<std::pair<std::string, std::string>> v = {{"a",  "b"},
                                                                      {"aa", "bb"}};
                t.insert(std::begin(v), std::end(v));
                StringTable u = t;
                EXPECT_EQ(u, t);
            }

            TEST(Table, Equality2) {
                StringTable t;
                std::vector<std::pair<std::string, std::string>> v1 = {{"a",  "b"},
                                                                       {"aa", "bb"}};
                t.insert(std::begin(v1), std::end(v1));
                StringTable u;
                std::vector<std::pair<std::string, std::string>> v2 = {{"a",  "a"},
                                                                       {"aa", "aa"}};
                u.insert(std::begin(v2), std::end(v2));
                EXPECT_NE(u, t);
            }

            TEST(Table, Equality3) {
                StringTable t;
                std::vector<std::pair<std::string, std::string>> v1 = {{"b",  "b"},
                                                                       {"bb", "bb"}};
                t.insert(std::begin(v1), std::end(v1));
                StringTable u;
                std::vector<std::pair<std::string, std::string>> v2 = {{"a",  "a"},
                                                                       {"aa", "aa"}};
                u.insert(std::begin(v2), std::end(v2));
                EXPECT_NE(u, t);
            }

            TEST(Table, NumDeletedRegression) {
                IntTable t;
                t.emplace(0);
                t.erase(t.find(0));
                // construct over a deleted slot.
                t.emplace(0);
                t.clear();
            }

            TEST(Table, FindFullDeletedRegression) {
                IntTable t;
                for (int i = 0; i < 1000; ++i) {
                    t.emplace(i);
                    t.erase(t.find(i));
                }
                EXPECT_EQ(0, t.size());
            }

            TEST(Table, ReplacingDeletedSlotDoesNotRehash) {
                size_t n;
                {
                    // Compute n such that n is the maximum number of elements before rehash.
                    IntTable t;
                    t.emplace(0);
                    size_t c = t.bucket_count();
                    for (n = 1; c == t.bucket_count(); ++n)
                        t.emplace(n);
                    --n;
                }
                IntTable t;
                t.rehash(n);
                const size_t c = t.bucket_count();
                for (size_t i = 0; i != n; ++i)
                    t.emplace(i);
                EXPECT_EQ(c, t.bucket_count()) << "rehashing threshold = " << n;
                t.erase(0);
                t.emplace(0);
                EXPECT_EQ(c, t.bucket_count()) << "rehashing threshold = " << n;
            }

            TEST(Table, NoThrowMoveConstruct) {
                ASSERT_TRUE(
                        std::is_nothrow_copy_constructible<abel::hash<std::string_view>>::value);
                ASSERT_TRUE(std::is_nothrow_copy_constructible<
                        std::equal_to<std::string_view>>
                                    ::value);
                ASSERT_TRUE(std::is_nothrow_copy_constructible<std::allocator<int>>::value);
                EXPECT_TRUE(std::is_nothrow_move_constructible<StringTable>::value);
            }

            TEST(Table, NoThrowMoveAssign) {
                ASSERT_TRUE(
                        std::is_nothrow_move_assignable<abel::hash<std::string_view>>::value);
                ASSERT_TRUE(
                        std::is_nothrow_move_assignable<std::equal_to<std::string_view>>::value);
                ASSERT_TRUE(std::is_nothrow_move_assignable<std::allocator<int>>::value);
                ASSERT_TRUE(
                        abel::allocator_traits<std::allocator<int>>::is_always_equal::value);
                EXPECT_TRUE(std::is_nothrow_move_assignable<StringTable>::value);
            }

            TEST(Table, NoThrowSwappable) {
                ASSERT_TRUE(
                        container_internal::IsNoThrowSwappable<abel::hash<std::string_view>>());
                ASSERT_TRUE(container_internal::IsNoThrowSwappable<
                        std::equal_to<std::string_view>>
                                    ());
                ASSERT_TRUE(container_internal::IsNoThrowSwappable<std::allocator<int>>());
                EXPECT_TRUE(container_internal::IsNoThrowSwappable<StringTable>());
            }

            TEST(Table, HeterogeneousLookup) {
                struct Hash {
                    size_t operator()(int64_t i) const { return i; }

                    size_t operator()(double i) const {
                        ADD_FAILURE();
                        return i;
                    }
                };
                struct Eq {
                    bool operator()(int64_t a, int64_t b) const { return a == b; }

                    bool operator()(double a, int64_t b) const {
                        ADD_FAILURE();
                        return a == b;
                    }

                    bool operator()(int64_t a, double b) const {
                        ADD_FAILURE();
                        return a == b;
                    }

                    bool operator()(double a, double b) const {
                        ADD_FAILURE();
                        return a == b;
                    }
                };

                struct THash {
                    using is_transparent = void;

                    size_t operator()(int64_t i) const { return i; }

                    size_t operator()(double i) const { return i; }
                };
                struct TEq {
                    using is_transparent = void;

                    bool operator()(int64_t a, int64_t b) const { return a == b; }

                    bool operator()(double a, int64_t b) const { return a == b; }

                    bool operator()(int64_t a, double b) const { return a == b; }

                    bool operator()(double a, double b) const { return a == b; }
                };

                raw_hash_set<IntPolicy, Hash, Eq, Alloc<int64_t>> s{0, 1, 2};
                // It will convert to int64_t before the query.
                EXPECT_EQ(1, *s.find(double{1.1}));

                raw_hash_set<IntPolicy, THash, TEq, Alloc<int64_t>> ts{0, 1, 2};
                // It will try to use the double, and fail to find the object.
                EXPECT_TRUE(ts.find(1.1) == ts.end());
            }

            template<class Table>
            using CallFind = decltype(std::declval<Table &>().find(17));

            template<class Table>
            using CallErase = decltype(std::declval<Table &>().erase(17));

            template<class Table>
            using CallExtract = decltype(std::declval<Table &>().extract(17));

            template<class Table>
            using CallPrefetch = decltype(std::declval<Table &>().prefetch(17));

            template<class Table>
            using CallCount = decltype(std::declval<Table &>().count(17));

            template<template<typename> class C, class Table, class = void>
            struct VerifyResultOf : std::false_type {
            };

            template<template<typename> class C, class Table>
            struct VerifyResultOf<C, Table, abel::void_t<C<Table>>> : std::true_type {
            };

            TEST(Table, HeterogeneousLookupOverloads) {
                using NonTransparentTable =
                raw_hash_set<StringPolicy, abel::hash<std::string_view>,
                        std::equal_to<std::string_view>, std::allocator<int>>;

                EXPECT_FALSE((VerifyResultOf<CallFind, NonTransparentTable>()));
                EXPECT_FALSE((VerifyResultOf<CallErase, NonTransparentTable>()));
                EXPECT_FALSE((VerifyResultOf<CallExtract, NonTransparentTable>()));
                EXPECT_FALSE((VerifyResultOf<CallPrefetch, NonTransparentTable>()));
                EXPECT_FALSE((VerifyResultOf<CallCount, NonTransparentTable>()));

                using TransparentTable = raw_hash_set<
                        StringPolicy,
                        abel::container_internal::hash_default_hash<std::string_view>,
                        abel::container_internal::hash_default_eq<std::string_view>,
                        std::allocator<int>>;

                EXPECT_TRUE((VerifyResultOf<CallFind, TransparentTable>()));
                EXPECT_TRUE((VerifyResultOf<CallErase, TransparentTable>()));
                EXPECT_TRUE((VerifyResultOf<CallExtract, TransparentTable>()));
                EXPECT_TRUE((VerifyResultOf<CallPrefetch, TransparentTable>()));
                EXPECT_TRUE((VerifyResultOf<CallCount, TransparentTable>()));
            }

// TODO(alkis): Expand iterator tests.
            TEST(Iterator, IsDefaultConstructible) {
                StringTable::iterator i;
                EXPECT_TRUE(i == StringTable::iterator());
            }

            TEST(ConstIterator, IsDefaultConstructible) {
                StringTable::const_iterator i;
                EXPECT_TRUE(i == StringTable::const_iterator());
            }

            TEST(Iterator, ConvertsToConstIterator) {
                StringTable::iterator i;
                EXPECT_TRUE(i == StringTable::const_iterator());
            }

            TEST(Iterator, Iterates) {
                IntTable t;
                for (size_t i = 3; i != 6; ++i)
                    EXPECT_TRUE(t.emplace(i).second);
                EXPECT_THAT(t, UnorderedElementsAre(3, 4, 5));
            }

            TEST(Table, Merge) {
                StringTable t1, t2;
                t1.emplace("0", "-0");
                t1.emplace("1", "-1");
                t2.emplace("0", "~0");
                t2.emplace("2", "~2");

                EXPECT_THAT(t1, UnorderedElementsAre(Pair("0", "-0"), Pair("1", "-1")));
                EXPECT_THAT(t2, UnorderedElementsAre(Pair("0", "~0"), Pair("2", "~2")));

                t1.merge(t2);
                EXPECT_THAT(t1, UnorderedElementsAre(Pair("0", "-0"), Pair("1", "-1"),
                                                     Pair("2", "~2")));
                EXPECT_THAT(t2, UnorderedElementsAre(Pair("0", "~0")));
            }

            TEST(Nodes, EmptyNodeType) {
                using node_type = StringTable::node_type;
                node_type n;
                EXPECT_FALSE(n);
                EXPECT_TRUE(n.empty());

                EXPECT_TRUE((std::is_same<node_type::allocator_type,
                        StringTable::allocator_type>::value));
            }

            TEST(Nodes, ExtractInsert) {
                constexpr char k0[] = "Very long std::string zero.";
                constexpr char k1[] = "Very long std::string one.";
                constexpr char k2[] = "Very long std::string two.";
                StringTable t = {{k0, ""},
                                 {k1, ""},
                                 {k2, ""}};
                EXPECT_THAT(t,
                            UnorderedElementsAre(Pair(k0, ""), Pair(k1, ""), Pair(k2, "")));

                auto node = t.extract(k0);
                EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));
                EXPECT_TRUE(node);
                EXPECT_FALSE(node.empty());

                StringTable t2;
                StringTable::insert_return_type res = t2.insert(std::move(node));
                EXPECT_TRUE(res.inserted);
                EXPECT_THAT(*res.position, Pair(k0, ""));
                EXPECT_FALSE(res.node);
                EXPECT_THAT(t2, UnorderedElementsAre(Pair(k0, "")));

                // Not there.
                EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));
                node = t.extract("Not there!");
                EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));
                EXPECT_FALSE(node);

                // Inserting nothing.
                res = t2.insert(std::move(node));
                EXPECT_FALSE(res.inserted);
                EXPECT_EQ(res.position, t2.end());
                EXPECT_FALSE(res.node);
                EXPECT_THAT(t2, UnorderedElementsAre(Pair(k0, "")));

                t.emplace(k0, "1");
                node = t.extract(k0);

                // Insert duplicate.
                res = t2.insert(std::move(node));
                EXPECT_FALSE(res.inserted);
                EXPECT_THAT(*res.position, Pair(k0, ""));
                EXPECT_TRUE(res.node);
                EXPECT_FALSE(node);
            }

            IntTable MakeSimpleTable(size_t size) {
                IntTable t;
                while (t.size() < size)
                    t.insert(t.size());
                return t;
            }

            std::vector<int> OrderOfIteration(const IntTable &t) {
                return {t.begin(), t.end()};
            }

// These IterationOrderChanges tests depend on non-deterministic behavior.
// We are injecting non-determinism from the pointer of the table, but do so in
// a way that only the page matters. We have to retry enough times to make sure
// we are touching different memory pages to cause the ordering to change.
// We also need to keep the old tables around to avoid getting the same memory
// blocks over and over.
            TEST(Table, IterationOrderChangesByInstance) {
                for (size_t size : {2, 6, 12, 20}) {
                    const auto reference_table = MakeSimpleTable(size);
                    const auto reference = OrderOfIteration(reference_table);

                    std::vector<IntTable> tables;
                    bool found_difference = false;
                    for (int i = 0; !found_difference && i < 5000; ++i) {
                        tables.push_back(MakeSimpleTable(size));
                        found_difference = OrderOfIteration(tables.back()) != reference;
                    }
                    if (!found_difference) {
                        FAIL()
                                        << "Iteration order remained the same across many attempts with size "
                                        << size;
                    }
                }
            }

            TEST(Table, IterationOrderChangesOnRehash) {
                std::vector<IntTable> garbage;
                for (int i = 0; i < 5000; ++i) {
                    auto t = MakeSimpleTable(20);
                    const auto reference = OrderOfIteration(t);
                    // Force rehash to the same size.
                    t.rehash(0);
                    auto trial = OrderOfIteration(t);
                    if (trial != reference) {
                        // We are done.
                        return;
                    }
                    garbage.push_back(std::move(t));
                }
                FAIL() << "Iteration order remained the same across many attempts.";
            }

// Verify that pointers are invalidated as soon as a second element is inserted.
// This prevents dependency on pointer stability on small tables.
            TEST(Table, UnstablePointers) {
                IntTable table;

                const auto addr = [&](int i) {
                    return reinterpret_cast<uintptr_t>(&*table.find(i));
                };

                table.insert(0);
                const uintptr_t old_ptr = addr(0);

                // This causes a rehash.
                table.insert(1);

                EXPECT_NE(old_ptr, addr(0));
            }

// Confirm that we assert if we try to erase() end().
            TEST(TableDeathTest, EraseOfEndAsserts) {
                // Use an assert with side-effects to figure out if they are actually enabled.
                bool assert_enabled = false;
                assert([&]() {
                    assert_enabled = true;
                    return true;
                }());
                if (!assert_enabled)
                    return;

                IntTable t;
                // Extra simple "regexp" as regexp support is highly varied across platforms.
                constexpr char kDeathMsg[] = "is_full";
                EXPECT_DEATH_IF_SUPPORTED(t.erase(t.end()), kDeathMsg);
            }


#ifdef ADDRESS_SANITIZER
            TEST(Sanitizer, PoisoningUnused) {
              IntTable t;
              t.reserve(5);
              // Insert something to force an allocation.
              int64_t& v1 = *t.insert(0).first;

              // Make sure there is something to test.
              ASSERT_GT(t.capacity(), 1);

              int64_t* slots = RawHashSetTestOnlyAccess::GetSlots(t);
              for (size_t i = 0; i < t.capacity(); ++i) {
                EXPECT_EQ(slots + i != &v1, __asan_address_is_poisoned(slots + i));
              }
            }

            TEST(Sanitizer, PoisoningOnErase) {
              IntTable t;
              int64_t& v = *t.insert(0).first;

              EXPECT_FALSE(__asan_address_is_poisoned(&v));
              t.erase(0);
              EXPECT_TRUE(__asan_address_is_poisoned(&v));
            }
#endif  // ADDRESS_SANITIZER

        }  // namespace
    }  // namespace container_internal

}  // namespace abel
